#include <algorithm>
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int>ans(nums.size()+1);
        if(nums.size()==0)return 0;
        ans[1]=nums[0];
        for(int i=1;i<ans.size();i++)
        {
            ans[i]=nums[i-1];
            ans[i]=max(ans[i],ans[i-1]+nums[i-1]);
        }
        int t=-1e5;
        for(int i=1;i<ans.size();i++)
        {
            if(ans[i]>t)t=ans[i];
        }
        return t;
    }
};